package gold.digger;

import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC823 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        Map<Integer, Long> memo = new HashMap<>();
        Map<Integer, Integer> numSet = new HashMap<>();
        int factor = 1000000007;

        public int numFactoredBinaryTrees(int[] arr) {
            Arrays.sort(arr);
            for (int i = 0; i < arr.length; i++) {
                numSet.put(arr[i], i);
            }

            long totalAns = 0;
            for (int i = arr.length - 1; i >= 0; i--) {
                totalAns = (totalAns + searchAnsCntDFS(arr, i)) % factor;
            }

            return ((int) totalAns);
        }

        public long searchAnsCntDFS(int[] arr, int curIdx) {
            if (memo.containsKey(arr[curIdx])) return memo.get(arr[curIdx]);
            long curAns = 1;
            boolean[] visited = new boolean[curIdx];
            for (int i = curIdx - 1; i >= 0; i--) {
                if (!visited[i] && arr[curIdx] % arr[i] == 0 && numSet.containsKey(arr[curIdx] / arr[i])) {
                    final long left = searchAnsCntDFS(arr, i);
                    final long right = searchAnsCntDFS(arr, numSet.get(arr[curIdx] / arr[i]));
                    if (i == numSet.get(arr[curIdx] / arr[i])) curAns += left * right;
                    else curAns = (curAns + left * right * 2) % factor;

                    visited[i] = true;
                    visited[numSet.get(arr[curIdx] / arr[i])] = true;
                }
            }

            memo.put(arr[curIdx], curAns);
            return curAns;
        }
    }

    public void run() {
        Solution solution = new Solution();
//        int[] arr = InputUtil.toIntegerArray("[2, 4]");
        int[] arr = InputUtil.toIntegerArray("[2, 4, 5, 10]");
        System.out.println(solution.numFactoredBinaryTrees(arr));
    }

    public static void main(String[] args) throws Exception {
        LC823 an = new LC823();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
